#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder);
TreeNode *ConstructSubTree(vector<int>::const_iterator preBegin, vector<int>::const_iterator preEnd,
    vector<int>::const_iterator inBegin, vector<int>::const_iterator inEnd);

int main(int argc, char** argv){




    return 0;
}

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder){
    return ConstructSubTree(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
}

TreeNode *ConstructSubTree(vector<int>::const_iterator preBegin, vector<int>::const_iterator preEnd,
    vector<int>::const_iterator inBegin, vector<int>::const_iterator inEnd){
        if(inBegin == inEnd){
            return NULL;
        }

        TreeNode *pRoot = new TreeNode(*preBegin);
        vector<int>::const_iterator iRootIn = find(inBegin, inEnd, pRoot->val);
        // left subtree
        if(iRootIn != inBegin){
            // has left subtree
            pRoot->left = ConstructSubTree(preBegin+1,preBegin+1+(iRootIn-inBegin),inBegin, iRootIn);
        }
        // right subtree
        if(iRootIn != (inEnd-1)){
            // has right subtree
            pRoot->right = ConstructSubTree(preBegin+1+(iRootIn-inBegin),preEnd, iRootIn+1, inEnd);
        }
        return pRoot;
}